//
//  40.数组中只出现一次的两个数字.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/27.
//

import Foundation
/*
 题目：一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 思路1：字典
 思路2：异或：时间复杂度为O(n),空间复杂度为O(1) a^b^a = a^a^b = b^a^a =b
    异或概念：对数组中所有数组进行异或（^）,异或异或是强调异，即相同为0,不同为1。 设a，b为任意两个数。相同两数异或为0(a^a = 0)，0与任何一个数异或为该数本身(a^0=a)。且异或符合交换律（a^b=b^a）。
    所以题目中数组所有数字异或后结果为两个不同的数进行异或。（设为a^b）
    异或后，从后往前，找到他们二进制中第一个为1的位置，该位置上两个数的二进制不一样否则不可能为1.（设该位置为k）为了划分出来两个数。
    然后重新对数组异或，但是在异或的时候，根据该位置（k上为1和0）来划分，最后会将这两数字划分开来。虽然其它的数也会划分开来，但是它们是成对划分的，无论在哪边都不影响最后结果。
 */
func offer_40() {
    print(Solution().findNumsAppearOnce2([1,4,1,6,2,2]))
}

fileprivate class Solution {
    func findNumsAppearOnce1(_ array: [Int]) -> [Int] {
        var dict = [Int: Int]()
        for num in array {
            if dict[num] == nil {
                dict[num] = 1
            } else {
                dict[num]! += 1
            }
        }
        return Array(dict.filter { $1 == 1 }.keys)
    }
    
    func findNumsAppearOnce2(_ array: [Int]) -> [Int] {
        let res = array.reduce(0) { $0 ^ $1 }
        var compare = 1
        while compare & res == 0 {
            compare <<= 1
        }
        var a = 0
        var b = 0
        for num in array {
            if num & compare == 0 {
                a ^= num
            } else {
                b ^= num
            }
        }
        return a < b ? [a, b] : [b, a]
    }
}


